package algorithm.MonotonePriorityStack.leetcode_84;

import java.util.Stack;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Stack < Integer > stack = new Stack < > ();
        int ans =0;
        for (int i = 0; i < n; i++){
            while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                int temp = stack.pop();
                int left = stack.isEmpty()?-1:stack.peek();
                ans = Math.max(ans, heights[temp]*(i-left-1));
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int temp = stack.pop();
            int left = stack.isEmpty()?-1:stack.peek();
            ans = Math.max(ans, heights[temp]*(n-left-1));
        }
        return ans;
    }
}